/*
 * This file is part of Cadmium.
 * Copyright (C) 2007-2010 Xavier Clerc.
 *
 * Cadmium is free software; you can redistribute it and/or modify
 * it under the terms of the GNU Lesser General Public License as published by
 * the Free Software Foundation; either version 3 of the License, or
 * (at your option) any later version.
 *
 * Cadmium is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

package fr.x9c.cadmium.primitives.num;

import fr.x9c.cadmium.kernel.Block;
import fr.x9c.cadmium.kernel.CodeRunner;
import fr.x9c.cadmium.kernel.Custom;
import fr.x9c.cadmium.kernel.Primitive;
import fr.x9c.cadmium.kernel.PrimitiveProvider;
import fr.x9c.cadmium.kernel.Value;
import fr.x9c.cadmium.util.Misc;

/**
 * This class implements all primitives for modules related to 'num' library.
 *
 * @author <a href="mailto:cadmium@x9c.fr">Xavier Clerc</a>
 * @version 1.2
 * @since 1.0
 */
@PrimitiveProvider
public final class Nat {

    /** Number of bytes per digit. */
    static final int DIGIT_SIZE_IN_BYTES = 4;

    /** Number of bits per digit. */
    private static final int BNG_BITS_PER_DIGIT = 32;

    /** Number of bits per half digit. */
    private static final int BNG_BITS_PER_HALF_DIGIT =
        Nat.BNG_BITS_PER_DIGIT / 2;

    /** Mask for digit low half. */
    private static final int BNG_LOW_HALF_MASK =
        (1 << Nat.BNG_BITS_PER_HALF_DIGIT) - 1;

    /** Mask for digit, when stored as a <tt>long</tt>. */
    private static final long BNG_DIGIT_MASK =
        (((long) 1) << Nat.BNG_BITS_PER_DIGIT) - 1;

    /**
     * No instance of this class.
     */
    private Nat() {
    } // end empty constructor

    /**
     * Initializes the library by registering the custom type "_nat".
     * @param ctxt context
     * @param unit ignored
     * @return <i>unit</i>
     */
    @Primitive
    public static Value initialize_nat(final CodeRunner ctxt,
                                       final Value unit) {
        ctxt.getContext().registerCustom(CustomNat.OPS);
        return Value.UNIT;
    } // end method 'initialize_nat(CodeRunner, Value)'

    /**
     * Creates a natural.
     * @param ctxt context
     * @param size size of natural
     * @return natural of given size
     */
    @Primitive
    public static Value create_nat(final CodeRunner ctxt,
                                   final Value size) {
        final int sz = size.asLong();
        final Block b = Block.createCustom(sz * 4, CustomNat.OPS);
        b.setCustom(new int[sz]);
        return Value.createFromBlock(b);
    } // end method 'create_nat(CodeRunner, Value)'

    /**
     * Returns the size of a natural.
     * @param ctxt context
     * @param nat natural to get size from
     * @return size of given natural
     */
    @Primitive
    public static Value length_nat(final CodeRunner ctxt,
                                   final Value nat) {
        return Value.createFromLong(nat.asBlock().getWoSize() - 1);
    } // end method 'length_nat(CodeRunner, Value)'

    /**
     * Sets a part of a natural to zero.
     * @param ctxt context
     * @param nat natural to modify
     * @param ofs offset of first digit to set to zero
     * @param len number digits to set to zero
     * @return <i>unit</i>
     */
    @Primitive
    public static Value set_to_zero_nat(final CodeRunner ctxt,
                                        final Value nat,
                                        final Value ofs,
                                        final Value len) {
        final int[] b = (int[]) nat.asBlock().asCustom();
        final int o = ofs.asLong();
        final int l = len.asLong();
        for (int i = 0; i < l; i++) {
            b[o + i] = 0;
        } // end for
        return Value.UNIT;
    } // end method 'set_to_zero_nat(CodeRunner, Value, Value, Value)'

    /**
     * Copies a part of a natural.
     * @param ctxt context
     * @param nat1 destination natural
     * @param ofs1 destination offset
     * @param nat2 source natural
     * @param ofs2 source offset
     * @param len number of digits to copy
     * @return <i>unit</i>
     */
    @Primitive
    public static Value blit_nat(final CodeRunner ctxt,
                                 final Value nat1,
                                 final Value ofs1,
                                 final Value nat2,
                                 final Value ofs2,
                                 final Value len) {
        System.arraycopy((int[]) nat2.asBlock().asCustom(),
                         ofs2.asLong(),
                         (int[]) nat1.asBlock().asCustom(),
                         ofs1.asLong(),
                         len.asLong());
        return Value.UNIT;
    } // end method 'blit_nat(CodeRunner, Value, Value, Value, Value, Value)'

    /**
     * Sets a digit of a natural.
     * @param ctxt context
     * @param nat natural to modify
     * @param ofs offset of digit to set
     * @param digit digit value
     * @return <i>unit</i>
     */
    @Primitive
    public static Value set_digit_nat(final CodeRunner ctxt,
                                      final Value nat,
                                      final Value ofs,
                                      final Value digit) {
        ((int[]) nat.asBlock().asCustom())[ofs.asLong()] = digit.asLong();
        return Value.UNIT;
    } // end method 'set_digit_nat(CodeRunner, Value, Value, Value)'

    /**
     * Returns a digit from a natural.
     * @param ctxt context
     * @param nat natural
     * @param ofs offset of digit to natural
     * @return the digit of <i>nat</i> at offset <i>ofs</i>
     */
    @Primitive
    public static Value nth_digit_nat(final CodeRunner ctxt,
                                      final Value nat,
                                      final Value ofs) {
        return Value.createFromLong(((int[]) nat.asBlock().asCustom())[ofs.asLong()]);
    } // end method 'nth_digit_nat(CodeRunner, Value, Value)'

    /**
     * Sets a digit of a natural.
     * @param ctxt context
     * @param nat natural to modify
     * @param ofs offset of digit to set
     * @param digit digit value
     * @return <i>unit</i>
     */
    @Primitive
    public static Value set_digit_nat_native(final CodeRunner ctxt,
                                             final Value nat,
                                             final Value ofs,
                                             final Value digit) {
        ((int[]) nat.asBlock().asCustom())[ofs.asLong()] = digit.asBlock().asNativeInt();
        return Value.UNIT;
    } // end method 'set_digit_nat_native(CodeRunner, Value, Value, Value)'

    /**
     * Returns a digit from a natural.
     * @param ctxt context
     * @param nat natural
     * @param ofs offset of digit to natural
     * @return the digit of <i>nat</i> at offset <i>ofs</i>
     */
    @Primitive
    public static Value nth_digit_nat_native(final CodeRunner ctxt,
                                             final Value nat,
                                             final Value ofs) {
        final Block b = Block.createCustom(Custom.INT_NAT_SIZE,
                                           Custom.INT_NAT_OPS);
        b.setNativeInt(((int[]) nat.asBlock().asCustom())[ofs.asLong()]);
        return Value.createFromBlock(b);
    } // end method 'nth_digit_nat_native(CodeRunner, Value, Value)'

    /**
     * Returns the number of digits of a natural.
     * @param ctxt context
     * @param nat natural to get number of digits from
     * @param ofs offset to compute number of digits from
     * @param len length of natural
     * @return return the number of digit of natural
     */
    @Primitive
    public static Value num_digits_nat(final CodeRunner ctxt,
                                       final Value nat,
                                       final Value ofs,
                                       final Value len) {
        final int[] b = (int[]) nat.asBlock().asCustom();
        final int o = ofs.asLong();
        int l = len.asLong();
        while (true) {
            if (l == 0) {
                return Value.ONE;
            } // end if
            if (b[o + l - 1] != 0) {
                return Value.createFromLong(l);
            } // end if
            l--;
        } // end while
    } // end method 'num_digits_nat(CodeRunner, Value, Value, Value)'

    /**
     * Returns the number of leading zero bits of a given digit.
     * @param ctxt context
     * @param nat natural to get number of leading zero bits from
     * @param ofs offset of digit to compute number of leading zero bits from
     * @return the number of leading zero bits of <i>nat</i>
     */
    @Primitive
    public static Value num_leading_zero_bits_in_digit(final CodeRunner ctxt,
                                                       final Value nat,
                                                       final Value ofs) {
        return Value.createFromLong(numLeadingZeroBitsInDigit(((int[]) nat.asBlock().asCustom())[ofs.asLong()]));
    } // end method 'num_leading_zero_bits_in_digit(CodeRunner, Value, Value)'

    /**
     * Tests if a given digit of a natural is an int value.
     * @param ctxt context
     * @param nat natural to test digit from
     * @param ofs offset of digit to test
     * @return {@link fr.x9c.cadmium.kernel.Value#TRUE} if the digit is an int,
     *         {@link fr.x9c.cadmium.kernel.Value#FALSE} otherwise
     */
    @Primitive
    public static Value is_digit_int(final CodeRunner ctxt,
                                     final Value nat,
                                     final Value ofs) {
        return Misc.signedToUnsigned(((int[]) nat.asBlock().asCustom())[ofs.asLong()]) <= (long) Value.MAX_LONG
            ? Value.TRUE
            : Value.FALSE;
    } // end method 'is_digit_int(CodeRunner, Value, Value)'

    /**
     * Tests if a given digit of a natural is equal to zero.
     * @param ctxt context
     * @param nat natural to test digit from
     * @param ofs offset of digit to test
     * @return {@link fr.x9c.cadmium.kernel.Value#TRUE} if the digit is zero,
     *         {@link fr.x9c.cadmium.kernel.Value#FALSE} otherwise
     */
    @Primitive
    public static Value is_digit_zero(final CodeRunner ctxt,
                                      final Value nat,
                                      final Value ofs) {
        return ((int[]) nat.asBlock().asCustom())[ofs.asLong()] == 0
            ? Value.TRUE
            : Value.FALSE;
    } // end method 'is_digit_zero(CodeRunner, Value, Value)'

    /**
     * Tests if a given digit of a natural is normalized.
     * @param ctxt context
     * @param nat natural to test digit from
     * @param ofs offset of digit to test
     * @return {@link fr.x9c.cadmium.kernel.Value#TRUE} if the digit is normalized,
     *         {@link fr.x9c.cadmium.kernel.Value#FALSE} otherwise
     */
    @Primitive
    public static Value is_digit_normalized(final CodeRunner ctxt,
                                            final Value nat,
                                            final Value ofs) {
        return (Misc.signedToUnsigned(((int[]) nat.asBlock().asCustom())[ofs.asLong()])
            & (((long) 1) << (Nat.BNG_BITS_PER_DIGIT - 1))) != 0
            ? Value.TRUE
            : Value.FALSE;
    } // end method 'is_digit_normalized(CodeRunner, Value, Value)'

    /**
     * Tests if a given digit of a natural is odd.
     * @param ctxt context
     * @param nat natural to test digit from
     * @param ofs offset of digit to test
     * @return {@link fr.x9c.cadmium.kernel.Value#TRUE} if the digit is odd,
     *         {@link fr.x9c.cadmium.kernel.Value#FALSE} otherwise
     */
    @Primitive
    public static Value is_digit_odd(final CodeRunner ctxt,
                                     final Value nat,
                                     final Value ofs) {
        return (((int[]) nat.asBlock().asCustom())[ofs.asLong()] & 1) != 0
            ? Value.TRUE
            : Value.FALSE;
    } // end method 'is_digit_odd(CodeRunner, Value, Value)'

    /**
     * Increments a natural.
     * @param ctxt context
     * @param nat natural to increment
     * @param ofs offset of digit to increment
     * @param len natural length
     * @param carry carry in (increment)
     * @return carry out
     */
    @Primitive
    public static Value incr_nat(final CodeRunner ctxt,
                                 final Value nat,
                                 final Value ofs,
                                 final Value len,
                                 final Value carry) {
        final int[] b = (int[]) nat.asBlock().asCustom();
        int o = ofs.asLong();
        int l = len.asLong();
        if ((carry == Value.ZERO) || (l == 0)) return carry;
        do {
            if (++b[o] != 0) {
                return Value.ZERO;
            } // end if
            o++;
        } while (--l != 0);
        return Value.ONE;
    } // end method 'incr_nat(CodeRunner, Value, Value, Value, Value)'

    /**
     * Adds two natural, storing result in the first one.
     * @param ctxt context
     * @param nat1 first natural
     * @param ofs1 offset in first natural
     * @param len1 length of first natural
     * @param nat2 second natural
     * @param ofs2 offset in second natural
     * @param len2 length of second natural
     * @param carry carry in
     * @return carry out
     */
    @Primitive
    public static Value add_nat(final CodeRunner ctxt,
                                final Value nat1,
                                final Value ofs1,
                                final Value len1,
                                final Value nat2,
                                final Value ofs2,
                                final Value len2,
                                final Value carry) {
        final int[] b1 = (int[]) nat1.asBlock().asCustom();
        final int[] b2 = (int[]) nat2.asBlock().asCustom();
        int o1 = ofs1.asLong();
        int o2 = ofs2.asLong();
        int l1 = len1.asLong();
        int l2 = len2.asLong();
        int c = carry.asLong();
        l1 -= l2;
        for (; l2 > 0; l2--, o1++, o2++) {
            { // BngAdd2Carry(b1[o1], c, b1[o1], b2[o2], c)
                final long tmp1 = Misc.signedToUnsigned(b1[o1]);
                final long tmp2 = (tmp1 + Misc.signedToUnsigned(b2[o2]))
                    & Nat.BNG_DIGIT_MASK;
                final long tmp3 = (tmp2 + c) & Nat.BNG_DIGIT_MASK;
                c = (tmp2 < tmp1 ? 1 : 0) + (tmp3 < tmp2 ? 1 : 0);
                b1[o1] = Misc.unsignedToSigned(tmp3);
            } // end BngAdd2Carry
        } // end for
        if ((c == 0) || (l1 == 0)) return Value.createFromLong(c);
        do {
            if (++b1[o1] != 0) return Value.ZERO;
            o1++;
        } while (--l1 != 0);
        return Value.ONE;
    } // end method 'add_nat(CodeRunner, Value, Value, Value, ...)'

    /**
     * Exact synonym of {@link #add_nat(CodeRunner, Value, Value, Value, Value, Value, Value, Value)}.
     */
    @Primitive
    public static Value add_nat_native(final CodeRunner ctxt,
                                       final Value nat1,
                                       final Value ofs1,
                                       final Value len1,
                                       final Value nat2,
                                       final Value ofs2,
                                       final Value len2,
                                       final Value carry) {
        return add_nat(ctxt, nat1, ofs1, len1, nat2, ofs2, len2, carry);
    } // end method 'add_nat_native(CodeRunner, Value, Value, Value, Value, ...)'

    /**
     * Complements a natural.
     * @param ctxt context
     * @param nat natural to complement
     * @param ofs offset in natural
     * @param len length of natural
     * @return <i>unit</i>
     */
    @Primitive
    public static Value complement_nat(final CodeRunner ctxt,
                                       final Value nat,
                                       final Value ofs,
                                       final Value len) {
        final int[] b = (int[]) nat.asBlock().asCustom();
        final int o = ofs.asLong();
        final int l = len.asLong();
        for (int i = 0; i < l; i++) {
            b[i + o] = ~b[i + o];
        } // end for
        return Value.UNIT;
    } // end method 'complement_nat(CodeRunner, Value, Value, Value)'

    /**
     * Decrements a natural.
     * @param ctxt context
     * @param nat natural to decrement
     * @param ofs offset of digit to decrement
     * @param len natural length
     * @param carry carry in (decrement)
     * @return carry out
     */
    @Primitive
    public static Value decr_nat(final CodeRunner ctxt,
                                 final Value nat,
                                 final Value ofs,
                                 final Value len,
                                 final Value carry) {
        final int[] b = (int[]) nat.asBlock().asCustom();
        int o = ofs.asLong();
        int l = len.asLong();
        final int c = 1 ^ carry.asLong();
        if ((c == 0) || (l == 0)) return carry;
        do {
            if (b[o]-- != 0) return Value.ONE;
            o++;
        } while (--l != 0);
        return Value.ZERO;
    } // end method 'decr_nat(CodeRunner, Value, Value, Value, Value)'

    /**
     * Substracts two naturals, storing result in the first one.
     * @param ctxt context
     * @param nat1 first natural
     * @param ofs1 offset in first natural
     * @param len1 length of first natural
     * @param nat2 second natural
     * @param ofs2 offset in second natural
     * @param len2 length of second natural
     * @param carry carry in
     * @return carry out
     */
    @Primitive
    public static Value sub_nat(final CodeRunner ctxt,
                                final Value nat1,
                                final Value ofs1,
                                final Value len1,
                                final Value nat2,
                                final Value ofs2,
                                final Value len2,
                                final Value carry) {
        return Value.createFromLong(subNat((int[]) nat1.asBlock().asCustom(),
                                           ofs1.asLong(),
                                           len1.asLong(),
                                           (int[]) nat2.asBlock().asCustom(),
                                           ofs2.asLong(),
                                           len2.asLong(),
                                           carry.asLong()));
    } // end method 'sub_nat(CodeRunner, Value, Value, Value, ...)'

    /**
     * Exact synonym of {@link #sub_nat(CodeRunner, Value, Value, Value, Value, Value, Value, Value)}.
     */
    @Primitive
    public static Value sub_nat_native(final CodeRunner ctxt,
                                       final Value nat1,
                                       final Value ofs1,
                                       final Value len1,
                                       final Value nat2,
                                       final Value ofs2,
                                       final Value len2,
                                       final Value carry) {
        return sub_nat(ctxt, nat1, ofs1, len1, nat2, ofs2, len2, carry);
    } // end method 'sub_nat_native(CodeRunner, Value, Value, Value, Value, ...)'

    /**
     * Multiplies two natural, storing result in the first one.
     * @param ctxt context
     * @param nat1 first natural
     * @param ofs1 offset in first natural
     * @param len1 length of first natural
     * @param nat2 second natural
     * @param ofs2 offset in second natural
     * @param len2 length of second natural
     * @param nat3 carry in natural
     * @param ofs3 offset in carry in natural
     * @return carry out
     */
    @Primitive
    public static Value mult_digit_nat(final CodeRunner ctxt,
                                       final Value nat1,
                                       final Value ofs1,
                                       final Value len1,
                                       final Value nat2,
                                       final Value ofs2,
                                       final Value len2,
                                       final Value nat3,
                                       final Value ofs3) {
        return Value.createFromLong(multDigitNat((int[]) nat1.asBlock().asCustom(),
                                                 ofs1.asLong(),
                                                 len1.asLong(),
                                                 (int[]) nat2.asBlock().asCustom(),
                                                 ofs2.asLong(),
                                                 len2.asLong(),
                                                 (int[]) nat3.asBlock().asCustom(),
                                                 ofs3.asLong()));
    } // end method 'mult_digit_nat(CodeRunner, Value, ...)'

    /**
     * Exact synonym of {@link #mult_digit_nat(CodeRunner, Value, Value, Value, Value, Value, Value, Value, Value)}.
     */
    @Primitive
    public static Value mult_digit_nat_native(final CodeRunner ctxt,
                                              final Value nat1,
                                              final Value ofs1,
                                              final Value len1,
                                              final Value nat2,
                                              final Value ofs2,
                                              final Value len2,
                                              final Value nat3,
                                              final Value ofs3) {
        return mult_digit_nat(ctxt, nat1, ofs1, len1, nat2, ofs2, len2, nat3, ofs3);
    } // end method 'mult_digit_nat_native(CodeRunner, Value, Value, Value, ...)'

    /**
     * Given three naturals <i>a</i>, <i>b</i>, and <i>c</i>, computes
     * <i>a + b * c</i> and stores it in <i>a</i>.
     * @param ctxt context
     * @param nat1 first natural
     * @param ofs1 offset in first natural
     * @param len1 length of first natural
     * @param nat2 second natural
     * @param ofs2 offset in second natural
     * @param len2 length of second natural
     * @param nat3 third natural
     * @param ofs3 offset in third natural
     * @param len3 length of third natural
     * @return carry out
     */
    @Primitive
    public static Value mult_nat(final CodeRunner ctxt,
                                 final Value nat1,
                                 final Value ofs1,
                                 final Value len1,
                                 final Value nat2,
                                 final Value ofs2,
                                 final Value len2,
                                 final Value nat3,
                                 final Value ofs3,
                                 final Value len3) {
        final int[] b1 = (int[]) nat1.asBlock().asCustom();
        final int[] b2 = (int[]) nat2.asBlock().asCustom();
        final int[] b3 = (int[]) nat3.asBlock().asCustom();
        int o1 = ofs1.asLong();
        final int o2 = ofs2.asLong();
        int o3 = ofs3.asLong();
        int l1 = len1.asLong();
        final int l2 = len2.asLong();
        int l3 = len3.asLong();
        long carry;
        for (carry = 0; l3 > 0; l3--, o3++, l1--, o1++) {
            carry = (carry + multDigitNat(b1, o1, l1, b2, o2, l2, b3, o3))
                & Nat.BNG_DIGIT_MASK;
        } // end for
        return Value.createFromLong((int) carry);
    } // end method 'mult_nat(CodeRunner, Value, ...)'

    /**
     * Exact synonym of {@link #mult_nat(CodeRunner, Value, Value, Value, Value, Value, Value, Value, Value, Value)}.
     */
    @Primitive
    public static Value mult_nat_native(final CodeRunner ctxt,
                                        final Value nat1,
                                        final Value ofs1,
                                        final Value len1,
                                        final Value nat2,
                                        final Value ofs2,
                                        final Value len2,
                                        final Value nat3,
                                        final Value ofs3,
                                        final Value len3) {
        return mult_nat(ctxt, nat1, ofs1, len1, nat2, ofs2, len2, nat3, ofs3, len3);
    } // end method 'mult_nat_native(CodeRunner, Value, Value, Value, Value, ...)'

    /**
     * Given two naturals <i>a</i>, and <i>b</i>, computes
     * <i>2 * a + b ** 2</i> and stores it in <i>a</i>.
     * @param ctxt context
     * @param nat1 first natural
     * @param ofs1 offset in first natural
     * @param len1 length of first natural
     * @param nat2 second natural
     * @param ofs2 offset in second natural
     * @param len2 length of second natural
     * @return carry out
     */
    @Primitive
    public static Value square_nat(final CodeRunner ctxt,
                                   final Value nat1,
                                   final Value ofs1,
                                   final Value len1,
                                   final Value nat2,
                                   final Value ofs2,
                                   final Value len2) {
        final int[] b1 = (int[]) nat1.asBlock().asCustom();
        final int[] b2 = (int[]) nat2.asBlock().asCustom();
        int o1 = ofs1.asLong();
        int o2 = ofs2.asLong();
        int l1 = len1.asLong();
        int l2 = len2.asLong();

        long carry1 = 0;
        long carry2;
        for (int i = 1; i < l2; i++) {
            final int aofs = 2 * i - 1;
            carry1 = (carry1 + multDigitNat(b1, o1 + aofs, l1 - aofs, b2,
                                            o2 + i, l2 - i, b2, o2 + i - 1))
                & Nat.BNG_DIGIT_MASK;
        } // end for
        carry1 = ((carry1 << 1) | shiftLeft(b1, o1, l1, 1))
            & Nat.BNG_DIGIT_MASK;
        carry2 = 0;
        long ph, pl;
        for (int i = 0; i < l2; i++) {
            final long d = Misc.signedToUnsigned(b2[o2 + i]);
            { // BngMult(ph, pl, d, d)
                final long p11 = ((d & Nat.BNG_LOW_HALF_MASK)
                                  * (d & Nat.BNG_LOW_HALF_MASK))
                    & Nat.BNG_DIGIT_MASK;
                final long p12 = ((d & Nat.BNG_LOW_HALF_MASK)
                                  * (d >> Nat.BNG_BITS_PER_HALF_DIGIT))
                    & Nat.BNG_DIGIT_MASK;
                final long p21 = ((d >> Nat.BNG_BITS_PER_HALF_DIGIT)
                                  * (d & Nat.BNG_LOW_HALF_MASK))
                    & Nat.BNG_DIGIT_MASK;
                final long p22 = ((d >> Nat.BNG_BITS_PER_HALF_DIGIT)
                                  * (d >> Nat.BNG_BITS_PER_HALF_DIGIT))
                    & Nat.BNG_DIGIT_MASK;
                ph = (p22
                      + (p12 >> Nat.BNG_BITS_PER_HALF_DIGIT)
                      + (p21 >> Nat.BNG_BITS_PER_HALF_DIGIT))
                    & Nat.BNG_DIGIT_MASK;
                { // BngAdd3(pl, ph, p11, p12 << BNG_BITS_PER_HALF_DIGIT, p21 << BNG_BITS_PER_HALF_DIGIT)
                    final long tmp1 = p11;
                    final long tmp2 = (tmp1 + ((p12 << Nat.BNG_BITS_PER_HALF_DIGIT) & Nat.BNG_DIGIT_MASK))
                        & Nat.BNG_DIGIT_MASK;
                    ph = (ph + (tmp2 < tmp1 ? 1 : 0)) & Nat.BNG_DIGIT_MASK;
                    final long tmp3 = (tmp2 + ((p21 << Nat.BNG_BITS_PER_HALF_DIGIT) & Nat.BNG_DIGIT_MASK))
                        & Nat.BNG_DIGIT_MASK;
                    ph = (ph + (tmp3 < tmp2 ? 1 : 0)) & Nat.BNG_DIGIT_MASK;
                    pl = tmp3;
                } // end BngAdd3
            } // end BngMult
            { // BngAdd2Carry(b1[o1], carry2, b1[o1], pl, carry2)
                final long tmp1 = Misc.signedToUnsigned(b1[o1]);
                final long tmp2 = (tmp1 + pl) & Nat.BNG_DIGIT_MASK;
                final long tmp3 = (tmp2 + carry2) & Nat.BNG_DIGIT_MASK;
                carry2 = (tmp2 < tmp1 ? 1 : 0) + (tmp3 < tmp2 ? 1 : 0);
                b1[o1] = Misc.unsignedToSigned(tmp3);
            } // end BngAdd2Carry
            o1++;
            { // BngAdd2Carry(b1[o1], carry2, b1[o1], ph, carry2)
                final long tmp1 = Misc.signedToUnsigned(b1[o1]);
                final long tmp2 = (tmp1 + ph) & Nat.BNG_DIGIT_MASK;
                final long tmp3 = (tmp2 + carry2) & Nat.BNG_DIGIT_MASK;
                carry2 = (tmp2 < tmp1 ? 1 : 0) + (tmp3 < tmp2 ? 1 : 0);
                b1[o1] = Misc.unsignedToSigned(tmp3);
            } // end BngAdd2Carry
            o1++;
        } // end for
        l1 -= 2 * l2;
        if ((l1 > 0) && (carry2 != 0)) {
            do {
                if (++b1[o1] != 0) { carry2 = 0; break; }
                o1++;
            } while (--l1 != 0);
        } // end if
        return Value.createFromLong(Misc.unsignedToSigned((carry1 + carry2) & Nat.BNG_DIGIT_MASK));
    } // end method 'square_nat(CodeRunner, Value, Value, ...)'

    /**
     * Exact synonym of {@link #square_nat(CodeRunner, Value, Value, Value, Value, Value, Value)}.
     */
    @Primitive
    public static Value square_nat_native(final CodeRunner ctxt,
                                          final Value nat1,
                                          final Value ofs1,
                                          final Value len1,
                                          final Value nat2,
                                          final Value ofs2,
                                          final Value len2) {
        return square_nat(ctxt, nat1, ofs1, len1, nat2, ofs2, len2);
    } // end method 'square_nat_native(CodeRunner, Value, Value, Value, Value, Value, Value)'

    /**
     * Performs a logical left shift over a natural.
     * @param ctxt context
     * @param nat1 natural to perform left shift over
     * @param ofs1 offset in natural
     * @param len1 length of natural
     * @param nat2 natural to store carry out
     * @param ofs2 offset of digit to store carry out
     * @param nbits amplitude of left shift
     * @return <i>unit</i>
     */
    @Primitive
    public static Value shift_left_nat(final CodeRunner ctxt,
                                       final Value nat1,
                                       final Value ofs1,
                                       final Value len1,
                                       final Value nat2,
                                       final Value ofs2,
                                       final Value nbits) {
        ((int[]) nat2.asBlock().asCustom())[ofs2.asLong()] =
            shiftLeft((int[]) nat1.asBlock().asCustom(),
                      ofs1.asLong(),
                      len1.asLong(),
                      nbits.asLong());
        return Value.UNIT;
    } // end method 'shift_left_nat(CodeRunner, Value, Value, ...)'

    /**
     * Exact synonym of {@link #shift_left_nat(CodeRunner, Value, Value, Value, Value, Value, Value)}.
     */
    @Primitive
    public static Value shift_left_nat_native(final CodeRunner ctxt,
                                              final Value nat1,
                                              final Value ofs1,
                                              final Value len1,
                                              final Value nat2,
                                              final Value ofs2,
                                              final Value nbits) {
        return shift_left_nat(ctxt, nat1, ofs1, len1, nat2, ofs2, nbits);
    } // end method 'shift_left_nat_native(CodeRunner, Value, Value, Value, Value, Value, Value)'

    /**
     * Given three naturals <i>q</i>, <i>r</i>, <i>a</i>, and <i>b</i>,
     * computes <i>a / b</i> and stores quotient and remainder in
     * <i>q</i> and <i>r</i>.
     * @param ctxt context
     * @param natq first natural
     * @param ofsq offset in first natural
     * @param natr second natural
     * @param ofsr offset in second natural
     * @param nat1 third natural
     * @param ofs1 offset in third natural
     * @param len1 length of third natural
     * @param nat2 fourth natural
     * @param ofs2 offset in fourth natural
     * @return carry out
     */
    @Primitive
    public static Value div_digit_nat(final CodeRunner ctxt,
                                      final Value natq,
                                      final Value ofsq,
                                      final Value natr,
                                      final Value ofsr,
                                      final Value nat1,
                                      final Value ofs1,
                                      final Value len1,
                                      final Value nat2,
                                      final Value ofs2) {
        final int[] a = (int[]) natq.asBlock().asCustom();
        final int aOfs = ofsq.asLong();
        final int[] b = (int[]) nat1.asBlock().asCustom();
        final int bOfs = ofs1.asLong();
        final int len = len1.asLong();
        final int tmp = ((int[]) nat2.asBlock().asCustom())[ofs2.asLong()];
        final int shift = numLeadingZeroBitsInDigit(tmp);
        long d = Misc.signedToUnsigned(tmp);
        d = (d << shift) & Nat.BNG_DIGIT_MASK;
        shiftLeft(b, bOfs, len, shift);
        final long rem =
            divRemNormDigit(a,
                            aOfs,
                            b,
                            bOfs,
                            len,
                            d) & Nat.BNG_DIGIT_MASK;
        shiftRight(b, bOfs, len, shift);
        ((int[]) natr.asBlock().asCustom())[ofsr.asLong()] =
            Misc.unsignedToSigned(rem >> shift);
        return Value.UNIT;
    } // end method 'div_digit_nat(CodeRunner, Value, Value, Value, ...)'

    /**
     * Exact synonym of {@link #div_digit_nat(CodeRunner, Value, Value, Value, Value, Value, Value, Value, Value, Value)}.
     */
    @Primitive
    public static Value div_digit_nat_native(final CodeRunner ctxt,
                                             final Value natq,
                                             final Value ofsq,
                                             final Value natr,
                                             final Value ofsr,
                                             final Value nat1,
                                             final Value ofs1,
                                             final Value len1,
                                             final Value nat2,
                                             final Value ofs2) {
        return div_digit_nat(ctxt, natq, ofsq, natr, ofsr, nat1, ofs1, len1, nat2, ofs2);
    } // end method 'div_digit_nat_native(CodeRunner, Value, Value, Value, ...)'

    /**
     * Given two naturals <i>n</i> and <i>d</i> of lengths <i>ln</i>
     * and <i>ld</i> , computes (a) <i>n / d</i> stored in <i>n</i>
     * at offset <i>ld</i> and (b) <i>n mod d</i> stored in <i>n</i>
     * at offset <i>0</i>.
     */
    @Primitive
    public static Value div_nat(final CodeRunner ctxt,
                                final Value nat1,
                                final Value ofs1,
                                final Value len1,
                                final Value nat2,
                                final Value ofs2,
                                final Value len2) {
        final int[] n = (int[]) nat1.asBlock().asCustom();
        final int[] d = (int[]) nat2.asBlock().asCustom();
        int nOfs = ofs1.asLong();
        int dOfs = ofs2.asLong();
        int nLen = len1.asLong();
        int dLen = len2.asLong();

        long topDen, quo, rem;

        final int shift = numLeadingZeroBitsInDigit(d[dOfs + dLen - 1]);
        shiftLeft(n, nOfs, nLen, shift);
        shiftLeft(d, dOfs, dLen, shift);
        if (dLen == 1) {
            n[nOfs] = Misc.unsignedToSigned(divRemNormDigit(n, nOfs + 1,
                                                            n, nOfs,
                                                            nLen,
                                                            Misc.signedToUnsigned(d[dOfs])));
        } else {
            topDen = Misc.signedToUnsigned(d[dOfs + dLen - 1]);
            for (int j = nLen - 1; j >= dLen; j--) {
                final int i = j - dLen;
                if (((topDen + 1) & Nat.BNG_DIGIT_MASK) == 0) {
                    quo = Misc.signedToUnsigned(n[nOfs + j]);
                } else {
                    { // BngDiv(quo, rem, n[nOfs + j] :: nh, n[nOfs + j - 1] :: nl, topDen + 1 :: dd) :: bng_div_aux
                        long nh = Misc.signedToUnsigned(n[nOfs + j]);
                        long nl = Misc.signedToUnsigned(n[nOfs + j - 1]);
                        final long dd = (topDen + 1) & Nat.BNG_DIGIT_MASK;
                        final long dl = dd & Nat.BNG_LOW_HALF_MASK;
                        final long dh = dd >> Nat.BNG_BITS_PER_HALF_DIGIT;
                        long qh = nh / (dh + 1);
                        final long nsaved = nl & Nat.BNG_LOW_HALF_MASK;
                        long ph = (qh * dh) & Nat.BNG_DIGIT_MASK;
                        long pl = (qh * dl) & Nat.BNG_DIGIT_MASK;
                        nh = (nh - ph) & Nat.BNG_DIGIT_MASK;
                        nl = ((nl >> Nat.BNG_BITS_PER_HALF_DIGIT)
                              | (nh << Nat.BNG_BITS_PER_HALF_DIGIT))
                            & Nat.BNG_DIGIT_MASK;
                        nh = nh >> Nat.BNG_BITS_PER_HALF_DIGIT;
                        nh = (nh - (nl < pl ? 1 : 0)) & Nat.BNG_DIGIT_MASK;
                        nl = (nl - pl) & Nat.BNG_DIGIT_MASK;
                        while ((nh != 0) || (nl >= dd)) {
                            nh = (nh - (nl < dd ? 1 : 0)) & Nat.BNG_DIGIT_MASK;
                            nl = (nl - dd) & Nat.BNG_DIGIT_MASK;
                            qh = (qh + 1) & Nat.BNG_DIGIT_MASK;
                        } // end while
                        long ql = nl / (dh + 1);
                        ph = (ql * dh) & Nat.BNG_DIGIT_MASK;
                        pl = (ql * dl) & Nat.BNG_DIGIT_MASK;
                        nl = (nl - ph) & Nat.BNG_DIGIT_MASK;
                        nh = nl >> Nat.BNG_BITS_PER_HALF_DIGIT;
                        nl = ((nl << Nat.BNG_BITS_PER_HALF_DIGIT) | nsaved)
                            & Nat.BNG_DIGIT_MASK;
                        nh = (nh - (nl < pl ? 1 : 0)) & Nat.BNG_DIGIT_MASK;
                        nl = (nl - pl) & Nat.BNG_DIGIT_MASK;
                        while ((nh != 0) || (nl >= dd)) {
                            nh = (nh - (nl < dd ? 1 : 0)) & Nat.BNG_DIGIT_MASK;
                            nl = (nl - dd) & Nat.BNG_DIGIT_MASK;
                            ql = (ql + 1) & Nat.BNG_DIGIT_MASK;
                        } // end while
                        quo = ((qh << Nat.BNG_BITS_PER_HALF_DIGIT) | ql)
                            & Nat.BNG_DIGIT_MASK;
                        // rem = nl; rem is not used afterwards
                    } // end BngDiv
                } // end if/else
                n[nOfs + j] = Misc.unsignedToSigned((Misc.signedToUnsigned(n[nOfs + j]) - multSubDigit(n, nOfs + i, dLen, d, dOfs, dLen, quo)) & Nat.BNG_DIGIT_MASK);
                while ((n[nOfs + j] != 0)
                       || (compareNat(n, nOfs + i, dLen, d, dOfs, dLen) >= 0)) {
                    quo = (quo + 1) & Nat.BNG_DIGIT_MASK;
                    n[nOfs + j] = Misc.unsignedToSigned(
                        Misc.signedToUnsigned(n[nOfs + j])
                        - (1 ^ subNat(n, nOfs + i, dLen, d, dOfs, dLen, 0)));
                } // end while
                n[nOfs + j] = Misc.unsignedToSigned(quo);
            } // end for
        } // end if/else
        shiftRight(n, nOfs, dLen, shift);
        shiftRight(d, dOfs, dLen, shift);
        return Value.UNIT;
    } // end method 'div_nat(CodeRunner, Value, Value, Value, Value, ...)'

    /**
     * Exact synonym of {@link #div_nat(CodeRunner, Value, Value, Value, Value, Value, Value)}.
     */
    @Primitive
    public static Value div_nat_native(final CodeRunner ctxt,
                                       final Value nat1,
                                       final Value ofs1,
                                       final Value len1,
                                       final Value nat2,
                                       final Value ofs2,
                                       final Value len2) {
        return div_nat(ctxt, nat1, ofs1, len1, nat2, ofs2, len2);
    } // end method 'div_nat_native(CodeRunner, Value, Value, Value, Value, Value, Value)'

    /**
     * Performs a logical right shift over a natural.
     * @param ctxt context
     * @param nat1 natural to perform right shift over
     * @param ofs1 offset in natural
     * @param len1 length of natural
     * @param nat2 natural to store carry out
     * @param ofs2 offset of digit to store carry out
     * @param nbits amplitude of right shift
     * @return <i>unit</i>
     */
    @Primitive
    public static Value shift_right_nat(final CodeRunner ctxt,
                                        final Value nat1,
                                        final Value ofs1,
                                        final Value len1,
                                        final Value nat2,
                                        final Value ofs2,
                                        final Value nbits) {
        ((int[]) nat2.asBlock().asCustom())[ofs2.asLong()] =
            shiftRight((int[]) nat1.asBlock().asCustom(),
                      ofs1.asLong(),
                      len1.asLong(),
                      nbits.asLong());
        return Value.UNIT;
    } // end method 'shift_right_nat(CodeRunner, Value, Value, ...)'

    /**
     * Exact synonym of {@link #shift_right_nat(CodeRunner, Value, Value, Value, Value, Value, Value)}.
     */
    @Primitive
    public static Value shift_right_nat_native(final CodeRunner ctxt,
                                               final Value nat1,
                                               final Value ofs1,
                                               final Value len1,
                                               final Value nat2,
                                               final Value ofs2,
                                               final Value nbits) {
        return shift_right_nat(ctxt, nat1, ofs1, len1, nat2, ofs2, nbits);
    } // end method 'shift_right_nat_native(CodeRunner, Value, Value, Value, Value, Value, Value)'

    /**
     * Compares two natural digits.
     * @param ctxt context
     * @param nat1 first natural to compare
     * @param ofs1 offset of digit in first natural
     * @param nat2 second natural to compare
     * @param ofs2 offset of digit in second natural
     * @return -1 if the first value is less than the second one <br/>
     *          0 if the two values are equal <br/>
     *          1 if the first value is greater than the second one
     */
    @Primitive
    public static Value compare_digits_nat(final CodeRunner ctxt,
                                           final Value nat1,
                                           final Value ofs1,
                                           final Value nat2,
                                           final Value ofs2) {
        final long d1 = Misc.signedToUnsigned(((int[]) nat1.asBlock().asCustom())[ofs1.asLong()]);
        final long d2 = Misc.signedToUnsigned(((int[]) nat2.asBlock().asCustom())[ofs2.asLong()]);
        if (d1 > d2) return Value.ONE;
        if (d1 < d2) return Value.MINUS_ONE;
        return Value.ZERO;
    } // end method 'compare_digits_nat(CodeRunner, Value, Value, ...)'

    /**
     * Compares two natural values.
     * @param ctxt context
     * @param nat1 first natural to compare
     * @param ofs1 offset in first natural
     * @param len1 length of first natural
     * @param nat2 second natural to compare
     * @param ofs2 offset in second natural
     * @param len2 length of second natural
     * @return -1 if the first value is less than the second one <br/>
     *          0 if the two values are equal <br/>
     *          1 if the first value is greater than the second one
     */
    @Primitive
    public static Value compare_nat(final CodeRunner ctxt,
                                    final Value nat1,
                                    final Value ofs1,
                                    final Value len1,
                                    final Value nat2,
                                    final Value ofs2,
                                    final Value len2) {
        return Value.createFromLong(compareNat((int[]) nat1.asBlock().asCustom(),
                                               ofs1.asLong(),
                                               len1.asLong(),
                                               (int[]) nat2.asBlock().asCustom(),
                                               ofs2.asLong(),
                                               len2.asLong()));
    } // end method 'compare_nat(CodeRunner, Value, Value, ...)'

    /**
     * Exact synonym of {@link #compare_nat(CodeRunner ctxt, Value, Value, Value, Value, Value, Value)}.
     */
    @Primitive
    public static Value compare_nat_native(final CodeRunner ctxt,
                                           final Value nat1,
                                           final Value ofs1,
                                           final Value len1,
                                           final Value nat2,
                                           final Value ofs2,
                                           final Value len2) {
        return compare_nat(ctxt, nat1, ofs1, len1, nat2, ofs2, len2);
    } // end method 'compare_nat_native(CodeRunner, Value, Value, Value, Value, Value, Value)'

    /**
     * Computes the 'and' of two natural digits and stores it in the first one.
     * @param ctxt context
     * @param nat1 first natural
     * @param ofs1 offset of digit in first natural
     * @param nat2 second natural
     * @param ofs2 offset of digit in second natural
     * @return <i>unit</i>
     */
    @Primitive
    public static Value land_digit_nat(final CodeRunner ctxt,
                                       final Value nat1,
                                       final Value ofs1,
                                       final Value nat2,
                                       final Value ofs2) {
        ((int[]) nat1.asBlock().asCustom())[ofs1.asLong()] &=
            ((int[]) nat2.asBlock().asCustom())[ofs2.asLong()];
        return Value.UNIT;
    } // end method 'land_digit_nat(CodeRunner, Value, Value, Value, Value)'

    /**
     * Computes the 'or' of two natural digits and stores it in the first one.
     * @param ctxt context
     * @param nat1 first natural
     * @param ofs1 offset of digit in first natural
     * @param nat2 second natural
     * @param ofs2 offset of digit in second natural
     * @return <i>unit</i>
     */
    @Primitive
    public static Value lor_digit_nat(final CodeRunner ctxt,
                                      final Value nat1,
                                      final Value ofs1,
                                      final Value nat2,
                                      final Value ofs2) {
        ((int[]) nat1.asBlock().asCustom())[ofs1.asLong()] |=
            ((int[]) nat2.asBlock().asCustom())[ofs2.asLong()];
        return Value.UNIT;
    } // end method 'lor_digit_nat(CodeRunner, Value, Value, Value, Value)'

    /**
     * Computes the 'xor' of two natural digits and stores it in the first one.
     * @param ctxt context
     * @param nat1 first natural
     * @param ofs1 offset of digit in first natural
     * @param nat2 second natural
     * @param ofs2 offset of digit in second natural
     * @return <i>unit</i>
     */
    @Primitive
    public static Value lxor_digit_nat(final CodeRunner ctxt,
                                       final Value nat1,
                                       final Value ofs1,
                                       final Value nat2,
                                       final Value ofs2) {
        ((int[]) nat1.asBlock().asCustom())[ofs1.asLong()] ^=
            ((int[]) nat2.asBlock().asCustom())[ofs2.asLong()];
        return Value.UNIT;
    } // end method 'lxor_digit_nat(CodeRunner, Value, Value, Value, Value)'

    /**
     * Returns the number of leading zero bits of a given digit.
     * @param digit natural to get number of leading zero bits from
     * @return the number of leading zero bits of <i>digit</i>
     */
    private static int numLeadingZeroBitsInDigit(final int digit) {
        int d = digit;
        int n = Nat.BNG_BITS_PER_DIGIT;
        if ((d & 0xFFFF0000) != 0) { n -= 16; d = d >> 16; }
        if ((d & 0xFF00) != 0) { n -= 8; d = d >> 8; }
        if ((d & 0xF0) != 0) { n -= 4; d = d >> 4; }
        if ((d & 0x0C) != 0) { n -= 2; d = d >> 2; }
        if ((d & 2) != 0) { n -= 1; d = d >> 1; }
        return n - d;
    } // end method 'numLeadingZeroBitsInDigit(int)'

    /**
     * Compares two natural values.
     * @param b1 digits of first natural to compare
     * @param ofs1 offset in first natural
     * @param len1 length of first natural
     * @param b2 digits of second natural to compare
     * @param ofs2 offset in second natural
     * @param len2 length of second natural
     * @return -1 if the first value is less than the second one <br/>
     *          0 if the two values are equal <br/>
     *          1 if the first value is greater than the second one
     */
    private static int compareNat(final int[] b1,
                                  final int ofs1,
                                  final int len1,
                                  final int[] b2,
                                  final int ofs2,
                                  final int len2) {
        final int o1 = ofs1;
        final int o2 = ofs2;
        int l1 = len1;
        int l2 = len2;

        while ((l1 > 0) && (b1[o1 + l1 - 1] == 0)) l1--;
        while ((l2 > 0) && (b2[o2 + l2 - 1] == 0)) l2--;
        if (l1 > l2) return 1;
        if (l1 < l2) return -1;

        while (l1 > 0) {
            l1--;
            final long da = Misc.signedToUnsigned(b1[o1 + l1]);
            final long db = Misc.signedToUnsigned(b2[o2 + l1]);
            if (da > db) return 1;
            if (da < db) return -1;
        } // end while

        return 0;
    } // end method 'compareNat(int[], int, int, int[], int, int)'

    /**
     * Substracts two naturals, storing result in the first one.
     * @param b1 digits of first natural
     * @param ofs1 offset in first natural
     * @param len1 length of first natural
     * @param b2 digits of second natural
     * @param ofs2 offset in second natural
     * @param len2 length of second natural
     * @param carry carry in
     * @return carry out
     */
    private static int subNat(final int[] b1,
                              final int ofs1,
                              final int len1,
                              final int[] b2,
                              final int ofs2,
                              final int len2,
                              final int carry) {
        int o1 = ofs1;
        int o2 = ofs2;
        int l1 = len1;
        int l2 = len2;
        int c = 1 ^ carry;
        l1 -= l2;
        for ( ; l2 > 0; l2--, o1++, o2++) {
            { // BngSub2Carry(b1[o1], c, b1[o1], b2[o2], c)
                final long tmp1 = Misc.signedToUnsigned(b1[o1]);
                final long tmp2 = Misc.signedToUnsigned(b2[o2]);
                final long tmp3 = (tmp1 - tmp2) & Nat.BNG_DIGIT_MASK;
                b1[o1] = Misc.unsignedToSigned((tmp3 - c) & Nat.BNG_DIGIT_MASK);
                c = (tmp1 < tmp2 ? 1 : 0) + (tmp3 < c ? 1 : 0);
            } // end BngSub2Carry
        } // end for
        if ((c == 0) || (l1 == 0)) return carry;
        do {
            if (b1[o1]-- != 0) return 1;
            o1++;
        } while (--l1 != 0);
        return 0;
    } // end method 'subNat(int[], int, int, int[], int, int, int)'

    /**
     * Multiplies two natural, storing result in the first one.
     * @param b1 digits of first natural
     * @param ofs1 offset in first natural
     * @param len1 length of first natural
     * @param b2 digits of second natural
     * @param ofs2 offset in second natural
     * @param len2 length of second natural
     * @param b3 digits of carry in natural
     * @param o3 offset in carry in natural
     * @return carry out
     */
    private static int multDigitNat(final int[] b1,
                                    final int ofs1,
                                    final int len1,
                                    final int[] b2,
                                    final int ofs2,
                                    final int len2,
                                    final int[] b3,
                                    final int o3) {
        int l1 = len1;
        int l2 = len2;
        int o1 = ofs1;
        int o2 = ofs2;
        final long d = Misc.signedToUnsigned(b3[o3]);
        l1 -= l2;
        long out;
        long carry;
        long ph, pl;
        for (out = 0; l2 > 0; l2--, o1++, o2++) {
            final long bd = Misc.signedToUnsigned(b2[o2]);
            { // BngMult(ph, pl, bd, d)
                final long p11 = ((bd & Nat.BNG_LOW_HALF_MASK)
                                  * (d & Nat.BNG_LOW_HALF_MASK))
                    & Nat.BNG_DIGIT_MASK;
                final long p12 = ((bd & Nat.BNG_LOW_HALF_MASK)
                                  * (d >> Nat.BNG_BITS_PER_HALF_DIGIT))
                    & Nat.BNG_DIGIT_MASK;
                final long p21 = ((bd >> Nat.BNG_BITS_PER_HALF_DIGIT)
                                  * (d & Nat.BNG_LOW_HALF_MASK))
                    & Nat.BNG_DIGIT_MASK;
                final long p22 = ((bd >> Nat.BNG_BITS_PER_HALF_DIGIT)
                                  * (d >> Nat.BNG_BITS_PER_HALF_DIGIT))
                    & Nat.BNG_DIGIT_MASK;
                ph = (p22
                    + (p12 >> Nat.BNG_BITS_PER_HALF_DIGIT)
                      + (p21 >> Nat.BNG_BITS_PER_HALF_DIGIT))
                    & Nat.BNG_DIGIT_MASK;
                { // BngAdd3(pl, ph, p11, p12 << BNG_BITS_PER_HALF_DIGIT, p21 << BNG_BITS_PER_HALF_DIGIT)
                    final long tmp1 = p11;
                    final long tmp2 = (tmp1 + ((p12 << Nat.BNG_BITS_PER_HALF_DIGIT) & Nat.BNG_DIGIT_MASK))
                        & Nat.BNG_DIGIT_MASK;
                    ph = (ph + (tmp2 < tmp1 ? 1 : 0)) & Nat.BNG_DIGIT_MASK;
                    final long tmp3 = (tmp2 + ((p21 << Nat.BNG_BITS_PER_HALF_DIGIT) & Nat.BNG_DIGIT_MASK))
                        & Nat.BNG_DIGIT_MASK;
                    ph = (ph + (tmp3 < tmp2 ? 1 : 0)) & Nat.BNG_DIGIT_MASK;
                    pl = tmp3;
                } // end BngAdd3
            } // end BngMult
            { // BngAdd3(b1[o1], ph, b1[o1], pl, out)
                final long tmp1 = Misc.signedToUnsigned(b1[o1]);
                final long tmp2 = (tmp1 + pl) & Nat.BNG_DIGIT_MASK;
                ph = (ph + (tmp2 < tmp1 ? 1 : 0)) & Nat.BNG_DIGIT_MASK;
                final long tmp3 = (tmp2 + out) & Nat.BNG_DIGIT_MASK;
                ph = (ph + (tmp3 < tmp2 ? 1 : 0)) & Nat.BNG_DIGIT_MASK;
                b1[o1] = Misc.unsignedToSigned(tmp3);
            } // end BngAdd3
            out = ph;
        } // end for
        if (l1 == 0) {
            return Misc.unsignedToSigned(out);
        } // end if
        { // BndAdd2(b1[o1], carry, b1[o1], out);
            final long tmp1 = Misc.signedToUnsigned(b1[o1]);
            final long tmp2 = (tmp1 + out) & Nat.BNG_DIGIT_MASK;
            carry = tmp2 < tmp1 ? 1 : 0;
            b1[o1] = Misc.unsignedToSigned(tmp2);
        } // end BndAdd2
        o1++;
        l1--;
        if ((carry == 0) || (l1 == 0)) {
            return (int) carry;
        } // end if
        do {
            if (++b1[o1] != 0) {
                return 0;
            } // end if
            o1++;
        } while (--l1 != 0);
        return 1;
    } // end method 'multDigitNat(int[], int, int, int[], int, int, int[], int)'

    /**
     * Performs a left shift over an array.
     * @param b array to perform shift over
     * @param ofs offset of shift
     * @param len length of shift
     * @param shift amplitude of shift (in bits)
     * @return carry out
     */
    private static int shiftLeft(final int[] b,
                                 final int ofs,
                                 final int len,
                                 final int shift) {
        int o = ofs;
        final int shift2 = Nat.BNG_BITS_PER_DIGIT - shift;
        int carry = 0;
        if (shift > 0) {
            for (int l = len; l > 0; l--, o++) {
                final int d = b[o];
                b[o] = (d << shift) | carry;
                carry = d >>> shift2;
            } // end for
        } // end if
        return carry;
    } // end method 'shiftLeft(int[], int, int, int)'

    /**
     * Performs a right shift over an array.
     * @param b array to perform shift over
     * @param ofs offset of shift
     * @param len length of shift
     * @param shift amplitude of shift (in bits)
     * @return carry out
     */
    private static int shiftRight(final int[] b,
                                  final int ofs,
                                  final int len,
                                  final int shift) {
        int l = len;
        final int shift2 = Nat.BNG_BITS_PER_DIGIT - shift;
        int carry = 0;
        if (shift > 0) {
            for (int o = ofs + l - 1; l > 0; l--, o--) {
                final int d = b[o];
                b[o] = (d >>> shift) | carry;
                carry = d << shift2;
            } // end for
        } // end if
        return carry;
    } // end method 'shiftRight(int[], int, int, int)'

    /**
     * Given two natural <i>a</i> and <i>b</i>, and a digit <i>d</i>, computes
     * <i>b / d</i> and stores it in <i>a</i>.
     * @param a first natural
     * @param aOfs offset in first natural
     * @param b second natural
     * @param bOfs offset in second natural
     * @param len length of both naturals
     * @param d digit
     * @return carry out
     */
    private static long divRemNormDigit(final int[] a,
                                        final int aOfs,
                                        final int[] b,
                                        final int bOfs,
                                        final int len,
                                        final long d) {
        long topDigit = Misc.signedToUnsigned(b[bOfs + len - 1]);
        long quo;
        long rem;
        long qh, ql, ph, pl;
        for (int i = len - 2; i >= 0; i--) {
            { // BngDiv(quo, rem, topDigit::nh, b[bOfs + i]::nl, d) :: bng_div_aux
                long nh = topDigit;
                long nl = Misc.signedToUnsigned(b[bOfs + i]);
                final long dl = (d & Nat.BNG_LOW_HALF_MASK)
                    & Nat.BNG_DIGIT_MASK;
                final long dh = (d >> Nat.BNG_BITS_PER_HALF_DIGIT)
                    & Nat.BNG_DIGIT_MASK;
                qh = nh / (dh + 1);
                final long nsaved = (nl & Nat.BNG_LOW_HALF_MASK)
                    & Nat.BNG_DIGIT_MASK;
                ph = (qh * dh) & Nat.BNG_DIGIT_MASK;
                pl = (qh * dl) & Nat.BNG_DIGIT_MASK;
                nh = (nh - ph) & Nat.BNG_DIGIT_MASK;
                nl = ((nl >> Nat.BNG_BITS_PER_HALF_DIGIT)
                      | (nh << Nat.BNG_BITS_PER_HALF_DIGIT))
                    & Nat.BNG_DIGIT_MASK;
                nh = nh >> Nat.BNG_BITS_PER_HALF_DIGIT;
                nh = (nh - (nl < pl ? 1 : 0)) & Nat.BNG_DIGIT_MASK;
                nl = (nl - pl) & Nat.BNG_DIGIT_MASK;
                while ((nh != 0) || (nl >= d)) {
                    nh = (nh - (nl < d ? 1 : 0)) & Nat.BNG_DIGIT_MASK;
                    nl = (nl - d) & Nat.BNG_DIGIT_MASK;
                    qh = (qh + 1) & Nat.BNG_DIGIT_MASK;
                } // end while
                ql = nl / (dh + 1);
                ph = (ql * dh) & Nat.BNG_DIGIT_MASK;
                pl = (ql * dl) & Nat.BNG_DIGIT_MASK;
                nl = (nl - ph) & Nat.BNG_DIGIT_MASK;
                nh = nl >> Nat.BNG_BITS_PER_HALF_DIGIT;
                nl = ((nl << Nat.BNG_BITS_PER_HALF_DIGIT) | nsaved)
                    & Nat.BNG_DIGIT_MASK;
                nh = (nh - (nl < pl ? 1 : 0)) & Nat.BNG_DIGIT_MASK;
                nl = (nl - pl) & Nat.BNG_DIGIT_MASK;
                while ((nh != 0) || (nl >= d)) {
                    nh = (nh - (nl < d ? 1 : 0)) & Nat.BNG_DIGIT_MASK;
                    nl = (nl - d) & Nat.BNG_DIGIT_MASK;
                    ql = (ql + 1) & Nat.BNG_DIGIT_MASK;
                } // end while
                quo = ((qh << Nat.BNG_BITS_PER_HALF_DIGIT) | ql)
                    & Nat.BNG_DIGIT_MASK;
                rem = nl;
            } // end BngDiv
            a[aOfs + i] = Misc.unsignedToSigned(quo);
            topDigit = rem;
        } // end for
        return topDigit;
    } // end method 'divRemNormDigit(int[], int, int[], int, int, long)'

    /**
     * Given two natural <i>a</i> and <i>b</i>, and a digit <i>d</i>, computes
     * <i>a - d * b</i> and stores it in <i>a</i>.
     * @param a first natural
     * @param ofs1 offset in first natural
     * @param len1 length of first natural
     * @param b second natural
     * @param ofs2 offset in second natural
     * @param len2 length of second natural
     * @param d digit
     * @return carry out
     */
    private static long multSubDigit(final int[] a,
                                     final int ofs1,
                                     final int len1,
                                     final int[] b,
                                     final int ofs2,
                                     final int len2,
                                     final long d) {
        int aLen = len1;
        int bLen = len2;
        int aOfs = ofs1;
        int bOfs = ofs2;
        long out, ph, pl, carry;

        aLen -= bLen;
        for (out = 0; bLen > 0; bLen--, aOfs++, bOfs++) {
            final long bd = Misc.signedToUnsigned(b[bOfs]);
            { // BngMult(ph, pl, bd, d)
                final long p11 = ((bd & Nat.BNG_LOW_HALF_MASK)
                                  * (d & Nat.BNG_LOW_HALF_MASK))
                    & Nat.BNG_DIGIT_MASK;
                final long p12 = ((bd & Nat.BNG_LOW_HALF_MASK)
                                  * (d >> Nat.BNG_BITS_PER_HALF_DIGIT))
                    & Nat.BNG_DIGIT_MASK;
                final long p21 = ((bd >> Nat.BNG_BITS_PER_HALF_DIGIT)
                                  * (d & Nat.BNG_LOW_HALF_MASK))
                    & Nat.BNG_DIGIT_MASK;
                final long p22 = ((bd >> Nat.BNG_BITS_PER_HALF_DIGIT)
                                  * (d >> Nat.BNG_BITS_PER_HALF_DIGIT))
                    & Nat.BNG_DIGIT_MASK;
                ph = (p22 + (p12 >> Nat.BNG_BITS_PER_HALF_DIGIT)
                      + (p21 >> Nat.BNG_BITS_PER_HALF_DIGIT))
                    & Nat.BNG_DIGIT_MASK;
                { // BngAdd3(pl, ph, p11, p12 << BNG_BITS_PER_HALF_DIGIT, p21 << BNG_BITS_PER_HALF_DIGIT)
                    final long tmp1 = p11;
                    final long tmp2 = (tmp1 + ((p12 << Nat.BNG_BITS_PER_HALF_DIGIT) & Nat.BNG_DIGIT_MASK))
                        & Nat.BNG_DIGIT_MASK;
                    ph = (ph + (tmp2 < tmp1 ? 1 : 0)) & Nat.BNG_DIGIT_MASK;
                    final long tmp3 = (tmp2 + ((p21 << Nat.BNG_BITS_PER_HALF_DIGIT) & Nat.BNG_DIGIT_MASK))
                        & Nat.BNG_DIGIT_MASK;
                    ph = (ph + (tmp3 < tmp2 ? 1 : 0)) & Nat.BNG_DIGIT_MASK;
                    pl = tmp3;
                } // end BngAdd3
            } // end BngMult
            { // BngSub3(a[aOfs], ph, a[aOfs], pl, out)
                final long tmp1 = Misc.signedToUnsigned(a[aOfs]);
                final long tmp2 = pl;
                final long tmp3 = out;
                final long tmp4 = (tmp1 - tmp2) & Nat.BNG_DIGIT_MASK;
                a[aOfs] =
                    Misc.unsignedToSigned((tmp4 - tmp3) & Nat.BNG_DIGIT_MASK);
                ph = (ph + (tmp1 < tmp2 ? 1 : 0) + (tmp4 < tmp3 ? 1 : 0))
                    & Nat.BNG_DIGIT_MASK;
            } // end BngSub3
            out = ph;
        } // end for
        if (aLen == 0) {
            return out;
        } // end if
        { // BngSub2(a[aOfs], carry, a[aOfs], out)
            final long tmp1 = Misc.signedToUnsigned(a[aOfs]);
            final long tmp2 = out;
            a[aOfs] = Misc.unsignedToSigned((tmp1 - tmp2) & Nat.BNG_DIGIT_MASK);
            carry = tmp1 < tmp2 ? 1 : 0;
        } // end BngSub2
        aOfs++;
        aLen--;
        if ((carry == 0) || (aLen == 0)) {
            return carry;
        } // end if
        do {
            if (a[aOfs]-- != 0) {
                return 0;
            } // end if
            aOfs++;
        } while (--aLen != 0);
        return 1;
    } // end method 'multSubDigit(int[], int, int, int[], int, int, long)'

} // end class 'Nat'
